package leetcode.leetcode234;

/**
 * @author czt
 * @version 1.0
 * @since 2024/12/18
 *
 * 判断是否回文链表
 */
public class Leetcode234 {

    /*
    1.找中间点
    2.中间点后半个链表反转
    3.返回后与原链表依次比较
     */

    public boolean isPalindrome(ListNode head) {
        ListNode middle = middle(head);
        ListNode reverse = reverse(middle);

        while (reverse != null) {
            if (head.val != reverse.val) {
                return false;
            }
            head = head.next;
            reverse = reverse.next;
        }

        return true;
    }

    // 找中间点
    private ListNode middle(ListNode head) {
        ListNode p1 = head;
        ListNode p2 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }

    // 反转链表
    private ListNode reverse(ListNode head) {

        ListNode n1 = null;

        ListNode p = head;
        while (p != null) {
            n1 = new ListNode(p.val, n1);
            p = p.next;
        }

        return n1;
    }
}
